<!DOCTYPE html>
<html lang="en">

<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>SSA for Trees</title>
<link rel="stylesheet" type="text/css" href="https://gcc.gnu.org/gcc.css" />
</head>

<body>
<h1>SSA for Trees</h1>

<h2>Table of Contents</h2>

<ul>
<li><a href="#news">Latest news (last updated: 2004-03-12)</a></li>
<li><a href="#intro">Introduction</a></li>
<li><a href="#documentation">Documentation</a></li>
<li><a href="#contributing">Contributing</a></li>
<li><a href="#stability">Branch stability</a></li>
<li><a href="#gimple">GENERIC and GIMPLE</a></li>
<li><a href="#ssa">SSA implementation</a></li>
<li><a href="#unparse">Unparsing GENERIC trees</a></li>
<li><a href="#tb">Tree Browser</a></li>
<li><a href="#status">Implementation Status (last updated: 2003-11-22)</a></li>
<li><a href="#todo">TODO list (last updated: 2003-12-27)</a></li>
</ul>

<hr />
<h2 id="news">Latest News</h2>

<dl>
<dt>2004-05-13</dt>
<dd><p>The branch is now closed.  Tree SSA has been <a
href="https://gcc.gnu.org/ml/gcc/2004-05/msg00679.html">merged</a> into
mainline.</p></dd>

<dt>2004-05-03</dt>
<dd><p>Merge status: <a href="https://gcc.gnu.org/ml/gcc/2004-05/msg00075.html">https://gcc.gnu.org/ml/gcc/2004-05/msg00075.html</a>.</p></dd>

<dt>2004-04-05</dt>
<dd><p>Merge status: <a href="https://gcc.gnu.org/ml/gcc/2004-04/msg00217.html">https://gcc.gnu.org/ml/gcc/2004-04/msg00217.html</a>.</p></dd>

<dt>2004-03-12</dt>
<dd><p>Merge status: <a
href="https://gcc.gnu.org/ml/gcc/2004-03/msg00596.html">https://gcc.gnu.org/ml/gcc/2004-03/msg00596.html</a>.</p></dd>

<dt>2004-02-25</dt>
<dd><p>The branch will be merged into mainline to become part of the next
    release of GCC.  As such, the branch is now <em>closed</em> to new
    development.</p>

    <p>The stabilization process will be driven by the merge criteria
    stated in <a href="https://gcc.gnu.org/ml/gcc/2004-02/msg01294.html">https://gcc.gnu.org/ml/gcc/2004-02/msg01294.html</a>.
    We expect to merge the branch into mainline by mid to late
    April.</p></dd>
</dl>

<hr />
<h3 id="intro">Introduction</h3>

<p>The goal of this project is to build an optimization framework for trees
based on the Static Single Assignment (SSA) form [<a
href="#cytron.ea-91">1</a>].  The implementation currently lives in the
<code>tree-ssa-20020619-branch</code> branch.</p>

<hr />
<h3 id="documentation">Documentation</h3>

<p>A high-level overview of GENERIC/GIMPLE and the SSA implementation may
be found in the <a href="https://gcc.gnu.org/pub/gcc/summit/2003/">Proceedings
of the 2003 GCC Developers Summit</a> (pages 171-193).</p>

<p>Internal design documentation is also available in the texinfo
documentation (<code>doc/gccint.info</code> in GCC's build directory).</p>

<p>Many further bits of information also can be found in the <a
href="https://gcc.gnu.org/wiki/GettingStarted">GCC Wiki</a>.</p>

<hr />
<h3 id="contributing">Contributing</h3>

<p>Checkout the <code>tree-ssa-20020619-branch</code> branch
in our respository.</p>

<p>All contributions to the branch must also comply with the
requirements detailed in the <a
href="../../contribute.html">contributing documentation</a>.</p>

<p>When posting to the development lists, please mark messages and patches with
<code>[tree-ssa]</code> in the subject.  As this is a branch, and not
the mainline, the usual maintainer rules do not apply.  This branch is
maintained by <a href="mailto:dnovillo@redhat.com">Diego Novillo
&lt;dnovillo@redhat.com&gt;</a>.  Approval from the usual maintainers will be
needed when submitting patches from the branch onto the mainline.</p>

<p>Current contributors to this project include 
Daniel Berlin, Steven Bosscher, Paul Brook, Zdenek Dvorak, Frank Eigler, Ben
Elliston, Andrew Haley, Richard Henderson, Graydon Hoare, Jan Hubicka, Aldy
Hernandez, Andreas Jaeger, Jeff Law, Andrew MacLeod, Toon Moene, Jason Merrill,
Diego Novillo, Sebastian Pop, Graham Stott and Jeff Sturm.</p>

<hr />
<h3 id="stability">Branch stability</h3>

<p>Every patch submitted for review must either fix a PR or adress one
of the issues mentioned in the <a
href="https://gcc.gnu.org/ml/gcc/2004-02/msg01294.html">merge criteria
document</a>.</p>

<p>Patches that break default bootstraps or introduce new
regressions will be removed (if a fix is not immediately
obvious).</p>

<p>There are regular mainline merges about 2 or 3 times a month.  The
latest merge tag is always added to GCC's version string.  A merge may
be postponed if there is major breakage in mainline.</p>


<hr />
<h2 id="gimple">GENERIC and GIMPLE</h2>

<p>While GCC trees contain sufficient information for
implementing SSA, there are two major problems that make this
difficult:</p>

<ul>
<li>There is no single tree representation in GCC.  Each front end
    defines its own trees.  This means that we would have to
    duplicate all this code for each front end.</li>

<li>Trees are arbitrarily complex.  This is a problem for
    optimizations that want to examine them.  They need to
    take into account many different variations.</li>
</ul>

<p>To address the first problem, we have created a common tree
representation called GENERIC that is meant to be able to represent all the
constructs needed by the different front ends while removing all the
language dependencies.  The design of GENERIC was discussed on the GCC
lists.  One of the main threads of discussion started with <a
href="https://gcc.gnu.org/ml/gcc/2002-07/msg00890.html">https://gcc.gnu.org/ml/gcc/2002-07/msg00890.html</a>.
A description of the current design can be found at
<a
href="https://gcc.gnu.org/ml/gcc/2002-08/msg01397.html">https://gcc.gnu.org/ml/gcc/2002-08/msg01397.html</a>.</p>

<p>To address the complexity problem we have implemented a new simplified
intermediate representation based on GENERIC. The IR, called GIMPLE, is a
very simple C-like three-address language that looks pretty straightforward
to analyze and keeps all the high-level attributes of data types.  GIMPLE
is derived from the SIMPLE representation proposed by the McCAT project out
of McGill University [<a href="#hendren.ea-92">2</a>].</p>

<p>The data structures are the same trees used by GCC, but we impose
rules on how the trees can be combined.  For instance, the
initial GENERIC representation for the expression:</p>

<pre>
a = b + c - d;
</pre>

<p>generates a single tree for the whole assignment statement.
The GIMPLE version of that expression generates 2 different
trees:</p>

<pre>
t1 = b + c;
a = t1 - d;
</pre>

<p>So, when examining expressions we can now assume that a
<code>PLUS</code> operation will always have exactly two operands that are
variables.  This also exposes other opportunities like finding common
expressions to eliminate (although it might also lead to code bloating, so
we need to be careful).  This new pass was discussed at length on the GCC
lists, starting with <a href="https://gcc.gnu.org/ml/gcc/2002-01/msg00082.html">https://gcc.gnu.org/ml/gcc/2002-01/msg00082.html</a>.</p>

<p>The conversion from GENERIC into GIMPLE trees is implemented in
<code>gimplify.c</code>.  Additionally, each front end may have a set of
language-specific helpers.  For instance, the C/Objective-C front ends contain the helper
functions in <code>c-simplify.c</code>, the C++ front end has its own in
<code>cp/cp-simplify.c</code>.  Predicates to determine whether a tree is
in GIMPLE form are defined in <code>tree-simple.[ch]</code>.</p>

<hr />
<h2 id="ssa">SSA implementation</h2>

<p>Having trees in GIMPLE form enables language-independent analysis
and transformation passes.  Currently, we are implementing an SSA pass
based on the algorithms described by Cytron <em>et. al.</em>
[<a href="#cytron-91">1</a>].</p>

<p>The graph below describes the process:</p>

<p><img src="tree-opt.png" alt=""/></p>

<p>The front ends described in the graph are just an example.  In
general, any front end that can emit functions-as-trees can be
converted to emit GENERIC trees.</p>

<p>Conversion to SSA form is a three step process driven from
<code>tree-optimize.c</code>:</p>

<ol>
<li>Convert the function into GIMPLE form.  Implemented in
<code>gimplify.c</code> and <code>c-simplify.c</code>.</li>
<li>Find variable references in the code.  Implemented in
<code>tree-dfa.c</code>.</li>
<li>Build a control-flow graph (CFG).  Implemented in <code>tree-cfg.c</code>.
This implementation uses the same <code>basic_block</code> structure used by
the RTL optimizers.  This allows us to share most of the existing CFG
code.</li>
<li>Rewrite the tree in SSA form.  Implemented in <code>tree-ssa.c</code>.</li>
</ol>

<hr />
<h2 id="unparse">Unparsing C trees</h2>

<p>The file <code>tree-pretty-print.c</code> implements several debugging
functions that given a GENERIC tree node, they print a C representation of
the tree.  The output is not meant to be compilable, but it is of great
help when debugging transformations done by the transformation passes.</p>

<hr />
<h2 id="tb">Tree Browser</h2>
For debugging, browsing, discovering, and playing with trees you can
use the <a href="tree-browser.html">Tree Browser</a> directly from gdb.

<hr />
<h2 id="status">Implementation Status</h2>

<p>This is a short list of the work that has already been finished or
is ongoing.</p>

<h3>Lowering of trees</h3>
<p>Lowering from the language specific tree representations for
C, C++, Java, Fortran 95, and Java bytecodes to GENERIC has been
implemented.  A more or less language-independent pass to lower
from GENERIC to GIMPLE has also been implemented.</p>

<h3>Into/out of SSA tree rewriting</h3>
<p>The CFG builder has been in place for a while now,
and most of the work that is done on it is tuning and speeding it
up where  possible.  Most of the DFA infrastructure is in place.
Type-based alias analysis has been implemented, but it needs some
work to be fast enough.  An initial implementation of Andersen
Points-to analysis is also available.  Rewriting the tree into SSA
form is finished.  Writing out of SSA form can now handle variables
with overlapping live ranges.  This means that most of the basic
infrastructure is in place.</p>

<h3>SSA Optimizations</h3>
<p>The following optimization passes have been implemented to date:</p>

<ul>
<li>CCP (sparse Conditional Constant Propagation)[<a
    href="#wegman.ea-91">4</a>].</li>
<li>DCE (Dead Code Elimination)[<a href="#morgan-98">3</a>].</li>
<li>PRE (Partial Redundancy Elimination)[<a href="#chow.ea-97">5</a>]
    with strength reduction.</li>
<li>Dominator-based optimizations such as copy propagation,
    constant propagation and redundancy elimination using value
    numbering [<a href="#morgan-98">3</a>].</li>
<li>Must-alias analysis, to convert pointer de-references into
    regular variable references whenever possible.</li>
<li>Scalar Replacement of Aggregates, to convert structure
    references into scalar references that can be optimized using
    the standard scalar passes.</li>
</ul>

<p>All passes are enabled by default at <code>-O1</code> and better.</p>

<h3>Testing framework</h3>
<p>Work on a framework for validation of the optimization passes has only
just started.  All analysis and optimization passes in the tree-ssa
framework have the ability to dump an annotated intermediate representation.
Support for scanning these tree dumps has been implemented for the
existing DejaGNU testing framework.</p>

<hr />
<h2 id="todo">TODO list</h2>

<p>This is a loosely organized list of unimplemented features,
possible improvement, and planned analyses and optimizations.
Suggestions for other passes and volunteers to help finish the
different passes are welcome.</p>

<h3>Medium and long term goals</h3>

<h4>Infrastructure</h4>

<dl>
<dt><em>Find and fix integration deficiencies</em></dt>
<dd>We have to integrate all the different passes to make one run
    after the other efficiently.  The integration work done so far has
    uncovered many bugs and inefficiencies in the way we build and
    maintain DFA/SSA information, and as more passes are implemented,
    we will probably find some more deficiencies that need to be
    addressed.</dd>
<dt><em>Tune RTL expanders to the subset of trees used by GIMPLE</em></dt>
<dd>This is best illustrated with an example.  In GIMPLE all loops are
    LOOP_EXPRs, a kind of tree node that was not produced by the C
    front end.  A simple patch reduced the number of INSNs for a loop
    header from 16 to 12.  It is very likely that other improvements
    like this are possible.</dd>
<dt><em>Analyse interactions between the tree and RTL optimizers</em></dt>
<dd>In the current implementation, no low-level (RTL) optimizations
    have been disabled yet, while the new infrastructure is already
    enabled.  So, there now is a new stage in the compile pipeline
    but nothing has been taken out yet.
    In theory, the tree optimizers should make some of the
    optimizations we try to do on RTL redundant for the front ends
    that already use the tree-ssa infrastructure.  But how exactly these
    two optimization infrastructures interact is not well understood
    yet.</dd>
<dt><em>Extend the testing framework</em></dt>
<dd>More analysis is required for a complete testing framework.  The
    framework will have to be updated to allow it to verify things like
    correct/optimal code motions.</dd>
<dt><em>Add test cases and consistency checks</em></dt>
<dd>Test cases that prove the correctness and efficiency of the
    optimization passes are especially welcome.</dd>
</dl>

<h4>Analyses</h4>

<dl>
<dt><em>SSA information for arrays</em></dt>
<dd>The existing implementation treats arrays as an opaque object.  A
    definition to an array location is treated as a definition for the
    whole array.</dd>
<dt><em>Pointer analysis (aliasing)</em></dt>
<dd>Dan Berlin is working on Andersen Points-to analysis.
    Unfortunately we cannot implement Steensgaard analysis due to
    patent issues.</dd>
</dl>

<h4>Basic scalar transformations</h4>

<dl>
<dt><em>GVN (Global Value Numbering)</em></dt>
<dd>Value numbering is used to detect equivalent expressions to eliminate
    redundancies. It assigns symbolic values to expressions such that if
    two expression have the same symbolic value, they compute the same
    value.</dd>
<dt><em>VRP (Value Range Propagation)[<a href="#patterson-95">6</a>]</em></dt>
<dd>This optimization tracks the weighted value ranges of variables through
    a program, much like constant propagation. These value ranges may be
    either numeric or symbolic in nature.</dd>
</dl>

<h4>Control transformations</h4>

<dl>
<dt><em>Loop nest optimizations</em></dt>
<dd>The <a href="lno.html">lno-branch</a> contains preliminary patches
    that aim at implementing tree level loop optimizations.</dd>
</dl>


<hr />
<h2>References</h2>

<dl>
<dt id="cytron.ea-91">[1]</dt>
<dd>R.&nbsp;Cytron, J.&nbsp;Ferrante, B.&nbsp;Rosen, M.&nbsp;Wegman, and K.&nbsp;Zadeck.
Efficiently Computing Static Single Assignment Form and the Control Dependence Graph.
<em>ACM Transactions on Programming Languages and Systems</em>, 13(4): 451-490, October 1991.</dd>

<dt id="hendren.ea-92">[2]</dt>
<dd>L.&nbsp;Hendren, C.&nbsp;Donawa, M.&nbsp;Emami, G.&nbsp;Gao, Justiani, and B.&nbsp;Sridharan.
Designing the McCAT compiler based on a family of structured intermediate representations.
In <em>Proceedings of the 5th International Workshop on Languages
 and Compilers for Parallel Computing</em>, pages 406-420. Lecture Notes in
 Computer Science, no. 457, Springer-Verlag, August 1992.</dd>

<dt id="morgan-98">[3]</dt>
<dd>Robert&nbsp;Morgan.
<em>Building an Optimizing Compiler</em>, Butterworth-Heinemann, 1998.</dd>

<dt id="wegman.ea-91">[4]</dt>
<dd>Mark&nbsp;N.&nbsp;Wegman and F.&nbsp;Kenneth&nbsp;Zadeck.
Constant Propagation with Conditional Branches.
<em>ACM Transactions on Programming Languages and Systems</em>, 13(2): 181-210, April 1991.</dd>

<dt id="chow.ea-97">[5]</dt>
<dd>Robbert&nbsp;Kennedy, Sun&nbsp;Chan, Shin-Ming&nbsp;Liu, Raymond&nbsp;Lo, Peng&nbsp;Tu, and Fred&nbsp;Chow.
Partial Redundancy Elimination in SSA Form.
<em>ACM Transactions on Programming Languages and Systems</em>, 21(3): 627-676, 1999.</dd>

<dt id="patterson-95">[6]</dt>
<dd>Jason&nbsp;R.&nbsp;C.&nbsp;Patterson.
Accurate Static Branch Prediction by Value Range Propagation.
<em>Proceedings of the ACM SIGPLAN '95 Conference on Programming Language Design and Implementation</em>, pages 67-78, June 1995.</dd>

</dl>

</body>
</html>
